package com.guiwu.jjj.leecode.easy;

import com.sun.org.apache.xpath.internal.operations.Bool;
import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils;
import sun.awt.image.ImageWatched;

import javax.sound.midi.Soundbank;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.function.Function;
import java.util.function.ToIntBiFunction;
import java.util.stream.Collectors;

/**
 * 解决方案
 *
 * @author jiangjinjian
 * @date 2023/2/9
 * @description
 */
public class Solution {
    //栈
    private Stack<Character> stack = new Stack<Character>();
    //括号map
    private static Map<Character, Character> bracketsMap = new HashMap<Character, Character>();

    //设置默认成对括号map
    static {
        bracketsMap.put('{', '}');
        bracketsMap.put('[', ']');
        bracketsMap.put('(', ')');
    }

    /**
     * 括号是否匹配 自己的解决方案
     *
     * @param s
     * @return
     */
    public boolean bracketsIsValid(String s) {
        //为空返回false
        if (s == null)
            return false;
        char[] charList = s.toCharArray();
        Boolean isOK = true;
        //记录左右括号数量,第一个记录左括号，第二个记录右括号
        int[] lengthList = new int[2];
        for (int i = 0; i < charList.length; i++) {
            //匹配到左括号入栈
            if ('(' == charList[i] || '{' == charList[i] || '[' == charList[i]) {
                stack.push(charList[i]);
                lengthList[0]++;
                //匹配到右括号出栈匹配括号有效性
            } else if (')' == charList[i] || '}' == charList[i] || ']' == charList[i]) {
                isOK = !stack.empty() ? bracketsMap.get(stack.pop()).equals(charList[i]) : false;
                lengthList[1]++;
            }
            //匹配到失败则结束循环
            if (!isOK) break;
        }
        //长度不等也默认不匹配
        if (lengthList[0] != lengthList[1])
            isOK = false;
        return isOK;
    }

    /**
     * 移动零 将数组所有零移至数组末尾，保持原来元素相对位置
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        //数组为null结束
        if (nums == null) {
            return;
        }
        int[] result = new int[nums.length];
        int index = 0;
        //数组获取不是0的值，剩下的空间默认就是0
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                result[index++] = nums[i];
            }
        }
        //将临时数组值赋值给nums中
        for (int i = 0; i < nums.length; i++) {
            nums[i] = result[i];
        }
    }

    /**
     * 寻找数组中消失的数字
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //数组为空返回null
        if (nums == null)
            return null;
        List<Integer> list = new ArrayList<>();
        //示例答案将+1运算用来了创建数组时，后面循环只有赋值，减少了10的5次方的+1运算
        int[] positionList = new int[nums.length];
        //将nums[i]的值赋值到positionList中的nums[i]
        //int数组默认为0，而记录nums中[1,num.length]数值缺失数字
        for (int i = 0; i < nums.length; i++) {
            positionList[nums[i] - 1] = nums[i];
        }
        for (int i = 0; i < positionList.length; i++) {
            if (positionList[i] == 0) {
                list.add(i + 1);
            }
        }
        return list;
    }

    /**
     * 两数之和
     * 传入nums数组以及目标值target，返回数组中两个元素值相加等于target的两个下标
     * 如：nums[i]+nums[j] == target return int[]{i,j}
     *
     * @param nums   数组
     * @param target 目标值
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        if (nums == null)
            return null;
        //初始化2个int大小空间的int数组，因为有且只返回两个下标
        int[] indexList = new int[2];
        //记录下标
        int index = -1;
        //标准答案是利用快排思想实现一层循环实现两数之和
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                //找到目标下标元素赋值下标且结束循环
                if (nums[i] + nums[j] == target) {
                    indexList[++index] = i;
                    indexList[++index] = j;
                    break;
                }
            }
            //找到下标值则结束循环
            if (index == 1) break;
        }
        return indexList;
    }

    /**
     * 爬楼梯，
     * 输入n为楼梯阶层，返回爬楼梯一共有几种方法，一次爬1到2层
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        //当楼梯数量小于等于0时无效
        if (n <= 0) return 0;
        if (n < 3) return n;
        //官方答案使用map结构存储 n - num n为输入值，num为方法数量
        //类似缓存机制的使用递归方法，即优先从map中读取数据，map中没数据再递归出结果
        //将斐波那契数列用循环实现
        int[] list = new int[n];
        list[0] = 1;
        list[1] = 2;
        for (int i = 2; i < n; i++) {
            list[i] = list[i - 1] + list[i - 2];
        }
        return list[n - 1];
    }

    /**
     * 链表
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 合并两个有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //其中一个为空返回另一个
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode node1 = list1;
        ListNode node2 = list2;
        ListNode head = new ListNode();
        ListNode tempNode = head;
        //使用快排思想对数据处理
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                tempNode.val = node1.val;
                node1 = node1.next;
            } else {
                tempNode.val = node2.val;
                node2 = node2.next;
            }
            if (node1 != null || node2 != null) {
                ListNode next = new ListNode();
                tempNode.next = next;
            }
            tempNode = tempNode.next;
        }
        while (node1 != null) {
            tempNode.val = node1.val;
            node1 = node1.next;
            if (node1 != null) {
                ListNode next = new ListNode();
                tempNode.next = next;
            }
            tempNode = tempNode.next;
        }
        while (node2 != null) {
            tempNode.val = node2.val;
            node2 = node2.next;
            if (node2 != null) {
                ListNode next = new ListNode();
                tempNode.next = next;
            }
            tempNode = tempNode.next;
        }
        return head;
    }

    /**
     * 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        //长度为一直接返回数组元素
        if (nums.length == 1) return nums[0];
        Boolean isRepeat = false;
        //官方答案通过异或实现
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j] && i != j) {
                    isRepeat = true;
                    break;
                }
            }
            if (!isRepeat) {
                return nums[i];
            } else isRepeat = false;
        }
        return -1;
    }

    /**
     * 树结构
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //存储树结构value值
    private List<Integer> numList = new ArrayList<>();

    /**
     * 二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        //递归出口
        if (root == null) return new ArrayList<>();
        inorderTraversal(root.left);
        numList.add(root.val);
        inorderTraversal(root.right);
        return numList;
    }

    /**
     * 多数元素，返回其中出现次数大于n/2的元素
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        //存储元素及其出现次数
        Map<Integer, Integer> majorMap = new HashMap<>();
        for (int num : nums) {
            Integer count = majorMap.get(num);
            //元素存在于map中数量加1否则加入到map中
            if (count != null) {
                majorMap.put(num, count + 1);
            } else {
                majorMap.put(num, 1);
            }
            if (majorMap.get(num) > nums.length / 2) {
                return num;
            }
        }
        return 0;
    }

    private Map<Integer, Integer> map = new HashMap<>();

    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        //空则结束操作
        if (nums == null) return null;
        //初始化列表
        List<List<Integer>> resultList = new ArrayList<>();
        //循环数组将数据加进map中
        for (int i = 0; i < nums.length; i++) {
            //将当前元素的相反数及下标加进map中
            map.put(-nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                //获取两者相加之后的所需元素的index
                Integer index = map.get(nums[i] + nums[j]);
                if (index != null && index != i && index != j) {
                    List<Integer> list = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[index]));
                    list = list.stream().sorted().collect(Collectors.toList());
                    resultList.add(list);
                }
            }
        }
        return resultList.stream().distinct().collect(Collectors.toList());
    }

    /**
     * 三数之和官方答案
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    /**
     * 两数相加
     * 传入两个非空链表，链表每一个节点只能存一位数，链表以倒序的方式存储的数字
     * 如：345  即：5->4->3
     * 使用String和BigInteger类，时间14ms
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //加多一个地址指定，避免修改l1和l2指定的地址
        ListNode firstNode = l1;
        ListNode secondNode = l2;
        String firstNodeValStr = "";
        String secondNodeValStr = "";
        //遍历赋值，通过将字符串放到末尾再利用字符串加法构建出数字字符串
        while (firstNode != null && secondNode != null) {
            firstNodeValStr = firstNode.val + firstNodeValStr;
            secondNodeValStr = secondNode.val + secondNodeValStr;
            firstNode = firstNode.next;
            secondNode = secondNode.next;
        }
        //继续遍历不为空的链表
        while (firstNode != null) {
            firstNodeValStr = firstNode.val + firstNodeValStr;
            firstNode = firstNode.next;
        }
        while (secondNode != null) {
            secondNodeValStr = secondNode.val + secondNodeValStr;
            secondNode = secondNode.next;
        }
        //利用BigInteger避免数字超出范围的情况
        BigInteger fistNum = new BigInteger(firstNodeValStr);
        BigInteger secondNum = new BigInteger(secondNodeValStr);
        String sum = fistNum.add(secondNum).toString();
        ListNode head = new ListNode(sum.charAt(sum.length() - 1) - 48);
        ListNode tempNode = head;
        //遍历字符串同时构建链表
        for (int i = sum.length() - 2; i >= 0; i--) {
            ListNode node = new ListNode(sum.charAt(i) - 48);
            tempNode.next = node;
            tempNode = tempNode.next;
        }
        return head;
    }

    /**
     * 两数相加
     * 传入两个非空链表，链表每一个节点只能存一位数，链表以倒序的方式存储的数字
     * 如：345  即：5->4->3
     * 完全使用int的解决方案，1ms
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode firstLink = l1;
        ListNode secondLink = l2;
        ListNode head = new ListNode();
        ListNode tempNode = head;
        //预留位，记录链表节点相加大于10该数则变为1，否则为0
        //因为两个个位数相加最大只能为18，所以不需要考虑其他情况
        int reserveNumber = 0;
        //遍历的同时，并创建新链表赋值
        while (firstLink != null && secondLink != null) {
            //获得当前数字相加结果及上一次相加的预留位数字
            int sum = firstLink.val + secondLink.val + reserveNumber;
            //记录是否进一位
            reserveNumber = sum / 10;
            //取个位作为节点的val
            ListNode node = new ListNode(sum % 10);
            //将节点尾插进链表中，再将tempNode移至下一节点
            tempNode.next = node;
            tempNode = tempNode.next;
            //将两个链表移至下一节点
            firstLink = firstLink.next;
            secondLink = secondLink.next;
        }
        //继续遍历剩下节点
        while (firstLink != null) {
            //获取节点val与预留位相加的结果
            int sum = firstLink.val + reserveNumber;
            reserveNumber = sum / 10;
            //取个位作为节点的val
            ListNode node = new ListNode(sum % 10);
            //将节点尾插进链表中，再将tempNode移至下一节点
            tempNode.next = node;
            tempNode = tempNode.next;
            //将两个链表移至下一节点
            firstLink = firstLink.next;
        }
        while (secondLink != null) {
            int sum = secondLink.val + reserveNumber;
            reserveNumber = sum / 10;
            ListNode node = new ListNode(sum % 10);
            tempNode.next = node;
            tempNode = tempNode.next;
            secondLink = secondLink.next;
        }
        //最后预留位再有1则继续增加节点
        if (reserveNumber == 1) {
            ListNode node = new ListNode(1);
            tempNode.next = node;
        }
        //去除头节点
        tempNode = head;
        head = head.next;
        tempNode = null;
        return head;
    }

    /**
     * 树的深度
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        //为空作为出口
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return leftDepth >= rightDepth ? leftDepth + 1 : rightDepth + 1;
    }


    /**
     * 相交链表，返回链表相交的节点，比较两个链表地址是否相同，即指向是否相同
     * 1ms 示例代码以类似思想实现算法，但是更加简单直接
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        //初始化默认A>B
        ListNode longNode = headA, shortNode = headB;
        int firstLength = getNodeLength(headA),
                secondLength = getNodeLength(headB);
        //如果B>A则交换指向
        if (secondLength > firstLength) {
            longNode = headB;
            shortNode = headA;
        }
        //再建一个变量指向短链表，使用这个变量遍历，防止shortNode改变指向
        ListNode tempShortNode = shortNode;
        //将长链表缩短到跟短链表一样的长度
        int differ = Math.abs(firstLength - secondLength);
        while (differ-- > 0)
            longNode = longNode.next;
        //记录最后不相等的节点
        ListNode lastUnEqualNode = new ListNode();
        while (longNode != null) {
            if (longNode != tempShortNode) {
                lastUnEqualNode = tempShortNode;
            }
            longNode = longNode.next;
            tempShortNode = tempShortNode.next;
        }
        if (lastUnEqualNode.val == 0)
            return shortNode;
        //遍历寻找第一次相交的节点
        while (shortNode != null && shortNode != lastUnEqualNode) {
            shortNode = shortNode.next;
        }
        return shortNode == null ? null : shortNode.next;
    }

    /**
     * 获取链表长度
     *
     * @param head
     * @return
     */
    public int getNodeLength(ListNode head) {
        if (head == null)
            return 0;
        //防止修改原来对象指向位置
        ListNode node = head;
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }
        return length;
    }

    /**
     * 回文链表
     * 9ms被人干死了
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        //空链表返回false
        if (head == null)
            return false;
        ListNode node = head;
        List<Integer> list = new ArrayList<>();
        //将值赋值给list
        while (node != null) {
            list.add(node.val);
            node = node.next;
        }
        for (int i = 0; i < list.size() / 2; i++) {
            if (!list.get(i).equals(list.get(list.size() - i - 1))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 回文链表，通过栈实现
     * 21ms被人干碎了
     *
     * @param head
     * @return
     */
    public boolean isPalindromeByStack(ListNode head) {
        //空链表返回false
        if (head == null)
            return false;
        ListNode node = head;
        //获取链表长度
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        //需要入栈的个数
        int needPushNumber = length / 2 + length % 2;
        Stack<Integer> stack = new Stack<>();
        node = head;
        while (node != null) {
            //先进栈
            if (needPushNumber-- > 0) {
                stack.push(node.val);
            } else {
                if (stack.pop() != node.val) return false;
            }
            //在链表长度为奇数的且进栈后，链表不需要指向下一个
            if (length % 2 != 0 && needPushNumber == 0) continue;
            node = node.next;
        }
        return true;
    }

    /**
     * 不含有重复字符的 最长子串 的长度
     * 超时了
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        //初始记录每个字符第一次出现的位置
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            //记录每个字符第一次出现的位置
            if (map.get(s.charAt(i)) == null) {
                map.put(s.charAt(i), i);
            }
        }
        int index = 0;
        List<Character> characters = new ArrayList<>();
        List<Character> tempChars = new ArrayList<>();
        while (index < s.length()) {
            if (!tempChars.contains(s.charAt(index))) {
                tempChars.add(s.charAt(index++));
            } else {
                //记录当前下标
                int currIndex = index;
                //获得当前字符在集合中下标
                int currCharIndex = Solution.getIndex(tempChars, s.charAt(currIndex));
                //index倒退到上一次该字符出现下标的下一位
                index = map.get(s.charAt(currIndex)) + 1;
                //保存该子字符串重复字符在字符串中的下标
                int targetIndex = currIndex - tempChars.size() + currCharIndex;
                map.put(s.charAt(currIndex), targetIndex);
                //更新最大子字符串
                characters = tempChars.size() > characters.size() ?
                        tempChars : characters;
                //重新记录
                tempChars = new ArrayList<>();
            }
        }
        if (characters.size() < tempChars.size()) {
            characters = tempChars;
        }
        System.out.println(characters);
        return characters.size();
    }

    /**
     * 获取集合中元素下标
     *
     * @param list
     * @param element
     * @param <T>
     * @return
     */
    public static <T> int getIndex(List<T> list, T element) {
        if (list == null) return -1;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(element)) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 判断二叉树是否对称
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        Solution.preOrder(root.left,
                "leftRight",
                leftList);
        Solution.preOrder(root.right,
                "rightLeft",
                rightList);
        return leftList.equals(rightList);
    }

    /**
     * 遍历节点
     *
     * @param root
     * @param mode
     * @param list
     */
    public static void preOrder(TreeNode root,
                                String mode,
                                List<Integer> list) {
        if (root == null) {
            list.add(-1);
            return;
        }
        list.add(root.val);
        if ("leftRight".equals(mode)) {
            preOrder(root.left, mode, list);
            preOrder(root.right, mode, list);
        } else if ("rightLeft".equals(mode)) {
            preOrder(root.right, mode, list);
            preOrder(root.left, mode, list);
        }
    }


    /**
     * 121. 买卖股票的最佳时机
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null) return 0;
        int min = prices[0], result = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            int next = prices[i + 1];
            int difference = next - min;
            result = difference > result ? difference : result;
            min = next < min ? next : min;
        }
        return result;
    }


    /**
     * 226. 翻转二叉树
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tempLeft = root.left;
        root.left = root.right;
        root.right = tempLeft;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    int max = 0;

    /**
     * 543. 二叉树的直径
     *
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        //获得左右子树的最大深度
        int childLength = Solution.maxDepth(root.left) + Solution.maxDepth(root.right);
        max = childLength > max ? childLength : max;
        int leftLength = diameterOfBinaryTree(root.left);
        int rightLength = diameterOfBinaryTree(root.right);
        return max;
    }

    /**
     * 617. 合并二叉树
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        return mergeTreesToRoot(root1, root2);
    }

    /**
     * 合并
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTreesToRoot(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 != null && root2 != null) {
            root1.val += root2.val;
            mergeTreesToRoot(root1.left, root2.left);
            mergeTreesToRoot(root1.right, root2.right);
        }
        return root1;
    }

    /**
     * 生成树
     *
     * @param root
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTreesToRoot(TreeNode root,
                                     TreeNode root1,
                                     TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 != null && root2 == null) {
            root.val = root1.val;
            root.left = root1.left != null ? new TreeNode() : null;
            root.right = root1.right != null ? new TreeNode() : null;
            mergeTreesToRoot(root.left, root1.left, null);
            mergeTreesToRoot(root.right, root1.right, null);
        } else if (root2 != null && root1 == null) {
            root.val = root2.val;
            root.left = root2.left != null ? new TreeNode() : null;
            root.right = root2.right != null ? new TreeNode() : null;
            mergeTreesToRoot(root.left, null, root2.left);
            mergeTreesToRoot(root.right, null, root2.right);
        } else {
            root.val = root1.val + root2.val;
            root.left = root2.left != null || root1.left != null ? new TreeNode() : null;
            root.right = root2.right != null || root1.right != null ? new TreeNode() : null;
            mergeTreesToRoot(root.left, root1.left, root2.left);
            mergeTreesToRoot(root.right, root1.right, root2.right);
        }
        return root;
    }

    /**
     * 进制转换
     *
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    public String solve(int M, int N) {
        if (N == 10) return M + "";
        Map<Integer, String> map = new HashMap<>();
        map.put(10, "A");
        map.put(11, "B");
        map.put(12, "C");
        map.put(13, "D");
        map.put(14, "E");
        map.put(15, "F");
        String operate = M > 0 ? "" : "-";
        M = Math.abs(M);
        String result = "";
        while (M / N != 0) {
            int temp = M % N;
            result = (temp >= 10 ? map.get(temp) : temp) + result;
            M = M / N;
        }
        if (M != 0) {
            result = (M >= 10 ? map.get(M) : M) + result;
        }
        return operate + result;
    }

    /**
     * @param numbers int整型一维数组
     * @param target  int整型
     * @return int整型一维数组
     */
    public int[] twoSum1(int[] numbers, int target) {
        if (numbers == null) return null;
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            int temp = target - numbers[i];
            map.put(temp, i);
        }
        for (int i = 0; i < numbers.length; i++) {
            Integer needIndex = map.get(numbers[i]);
            if (needIndex != null && needIndex != i) {
                int need = needIndex + 1;
                int other = i + 1;
                if (need > other) {
                    result[0] = other;
                    result[1] = need;
                } else {
                    result[0] = need;
                    result[1] = other;
                }
                return result;
            }
        }
        return null;
    }

    /**
     * 跳台阶
     *
     * @param target
     * @return
     */
    public int jumpFloor(int target) {
        if (target == 0) return 0;
        if (target == 1) return 1;
        if (target == 2) return 2;
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }

    /**
     * 括号的最大嵌套深度
     *
     * @param s
     * @return
     */
    public int maxDepth(String s) {
        if (s == null) return 0;
        List<Character> chars = new ArrayList<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '[':
                    ;
                case '{':
                    ;
                case '(':
                    ;
                    chars.add(s.charAt(i));
                    break;
                case '}':
                    ;
                case ']':
                    ;
                case ')': {
                    if (max < chars.size()) {
                        max = chars.size();
                    }
                    //删除最后一个
                    chars.remove(chars.size() - 1);
                }
                default:
                    break;
            }
        }
        return max;
    }

    /**
     * 有重复字符的排列组合
     *
     * @param S
     * @return
     */
    public String[] permutation(String S) {
        if (S.length() == 1) return new String[]{S};
        Map<String, String[]> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        map.put(S.substring(0, 1), new String[]{S.substring(0, 1)});
        for (int i = 1; i < S.length(); i++) {
            String[] tempStrList = map.get(S.substring(0, i));
            List<String> strList = new ArrayList<>();
            for (String str : tempStrList) {
                sb.append(str);

            }
        }
        return map.get(S);
    }

    /**
     * 平衡字符串
     *
     * @param s
     * @return
     */
    public int minimumDeletions(String s) {
        if (s == null) return 0;
        if (s.length() == 1) return 0;
        int aStart = 0, bStart = 0;
        int[] dpTable = new int[s.length() + 1];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                if (s.charAt(i - 1) == 'b') {
                    aStart = i;
                }
                if (dpTable[i] + 1 <= dpTable[bStart + 1] + aStart - bStart) {
                    dpTable[i + 1] = dpTable[i] + 1;
                } else dpTable[i + 1] = dpTable[i];
            } else {
                if (s.charAt(i - 1) == 'a') {
                    bStart = i;
                }
                dpTable[i + 1] = dpTable[i];
            }
        }
        return dpTable[s.length()];
    }


    private List<List<Integer>> res = new ArrayList<>();

    private boolean[] visited;

    /**
     * 组合
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> track = new ArrayList<>();
        visited = new boolean[n];
        backTrack(0, track, n, k);
        return res;
    }

    /**
     * 回溯
     *
     * @param index
     * @param track
     * @param n
     * @param k
     */
    public void backTrack(int index,
                          List<Integer> track,
                          int n,
                          int k) {
        //满足结束条件
        if (track.size() == k) {
            res.add(new ArrayList<>(track));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (visited[i - 1]
                    || (index > 0 && i < track.get(index - 1))) continue;
            track.add(i);
            visited[i - 1] = true;
            backTrack(index + 1, track, n, k);
            visited[i - 1] = false;
            track.remove(track.size() - 1);
        }
    }

    /**
     * 674. 最长连续递增序列
     *
     * @param nums
     * @return
     */
    public int findLengthOfLCIS(int[] nums) {
        if (nums == null) return 0;
        int max = 1, tempMax = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                tempMax++;
            } else {
                max = tempMax > max ? tempMax : max;
                tempMax = 1;
            }
        }
        return max > tempMax ? max : tempMax;
    }

    /**
     * 最长回文子串
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length() == 1) return s;
        List<String> strList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            int index = i;
            int j = s.length() - 1;
            while (s.charAt(i) != s.charAt(j)) {
                j--;
            }
            //如果j小于当前i则不可能有回文子串
            if (j < i) continue;
            if (j == i) strList.add(String.valueOf(s.charAt(i)));
            int temp = j;
            while (index < temp) {
                if (s.charAt(index) != s.charAt(temp)) {
                    break;
                }
                index++;
                temp--;
            }
            if (index == temp + 1 || index == temp) {
                strList.add(s.substring(i, j + 1));
            }
        }
        return strList.stream()
                .distinct()
                .max(Comparator.comparing(String::length)).get();
    }


    /**
     * 剑指 Offer 47. 礼物的最大价值
     *
     * @param grid
     * @return
     */
    public int maxValue(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] men = new int[n][m];
        return backTrack(grid, men, n - 1, m - 1);
    }


    /**
     * 回溯
     *
     * @param grid
     * @param n
     * @param m
     */
    public int backTrack(int[][] grid,
                         int[][] men,
                         int n,
                         int m) {
        if (n < 0 || m < 0) {
            return 0;
        }
        if (men[n][m] != 0) {
            return men[n][m];
        }
        if (n == 0 && m == 0)
            men[0][0] = grid[0][0];
        if (n == 0)
            men[0][m] = backTrack(grid, men, 0, m - 1) + grid[n][m];
        if (m == 0)
            men[n][0] = backTrack(grid, men, n - 1, 0) + grid[n][m];
        men[n][m] = Math.max(backTrack(grid, men, n, m - 1),
                backTrack(grid, men, n - 1, m)) + grid[n][m];
        return men[n][m];
    }

    /**
     * 76. 最小覆盖子串
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        return s;
    }

    /**
     * 剑指 Offer 32 - II. 从上到下打印二叉树 II
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        //初始化队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //初始化列表
        List<List<Integer>> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            result.add(list);
        }
        return result;
    }

    /**
     * 剑指 Offer 32 - III. 从上到下打印二叉树 III
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);
        int i = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            if (i % 2 != 0) {
                Collections.reverse(list);
            }
            result.add(list);
            ++i;
        }
        return result;
    }


    /**
     * 994. 腐烂的橘子
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int result = 0;
        if (isRottedAll(grid)) return result;
        Boolean[][] visited = new Boolean[n][m];
        Queue<Integer[]> queue = new LinkedList<>();
        List<Integer[]> startIndex = isRotedIndex(grid);
        if (startIndex.size() == 0) return -1;
        for (Integer[] index : startIndex) {
            queue.add(index);
        }
        while (!queue.isEmpty()) {
            Integer size = queue.size();
            while (size-- > 0) {
                Integer[] indexList = queue.poll();
                int i = indexList[0], j = indexList[1];
                if (grid[i][j] == 0) {
                    visited[i][j] = true;
                    continue;
                }
                if (visited[i][j] != null && visited[i][j] && grid[i][j] != 2) continue;
                if (nearbyAreRoted(grid, i, j)) continue;
                visited[i][j] = true;
                if (i + 1 < n) {
                    if (grid[i + 1][j] == 1 && grid[i][j] == 2) grid[i + 1][j] = 2;
                    queue.add(new Integer[]{i + 1, j});
                }
                if (j + 1 < m) {
                    if (grid[i][j + 1] == 1 && grid[i][j] == 2) grid[i][j + 1] = 2;
                    queue.add(new Integer[]{i, j + 1});
                }
                if (j - 1 >= 0) {
                    if (grid[i][j - 1] == 1 && grid[i][j] == 2) grid[i][j - 1] = 2;
                    queue.add(new Integer[]{i, j - 1});
                }
                if (i - 1 >= 0) {
                    if (grid[i - 1][j] == 1 && grid[i][j] == 2) grid[i - 1][j] = 2;
                    queue.add(new Integer[]{i - 1, j});
                }
            }
            result++;
            if (isRottedAll(grid))
                return result;
        }
        return isRottedAll(grid) ? result : -1;
    }

    /**
     * 判断附近节点是否都已经被腐化
     *
     * @param grid
     * @param i
     * @param j
     * @return
     */
    public Boolean nearbyAreRoted(int[][] grid, int i, int j) {
        if (i + 1 < grid.length) {
            if (grid[i + 1][j] == 1) return false;
        }
        if (j + 1 < grid[0].length) {
            if (grid[i][j + 1] == 1) return false;
        }
        if (j - 1 >= 0) {
            if (grid[i][j - 1] == 1) return false;
        }
        if (i - 1 >= 0) {
            if (grid[i - 1][j] == 1) return false;
        }
        return true;
    }

    /**
     * 已经腐烂的橘子，用于确认出发点
     *
     * @param grid
     * @return
     */
    public List<Integer[]> isRotedIndex(int[][] grid) {
        List<Integer[]> indexList = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    indexList.add(new Integer[]{i, j});
                }
            }
        }
        return indexList;
    }

    /**
     * 是否全部腐败
     *
     * @param grid
     * @return
     */
    public Boolean isRottedAll(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) return false;
            }
        }
        return true;
    }

    /**
     * 计算质数
     *
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        if (n == 0 || n == 1) return 0;
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (i == 2 || i == 3) {
                count++;
                continue;
            }
            boolean isPrimes = true;
            for (int j = 2; j <= i / 2; j++) {
                int number = i / j;
                if (number == (double) i / j) {
                    isPrimes = false;
                    break;
                }
            }
            if (isPrimes) {
                count++;
            }
        }
        return count;
    }

    /**
     * 杨辉三角
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0) return new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        //建立初态
        for (int i = 0; i < numRows; i++) {
            Integer[] nums = new Integer[i + 1];
            nums[0] = 1;
            nums[i] = 1;
            result.add(Arrays.asList(nums));
        }
        //3以下不需要计算
        if (numRows < 3) {
            return result.stream()
                    .limit(numRows)
                    .collect(Collectors.toList());
        }
        for (int i = 2; i < numRows; i++) {
            //当前行数据
            List<Integer> currNums = result.get(i);
            //上一行数据
            List<Integer> lastNums = result.get(i - 1);
            for (int j = 1; j < i; j++) {
                currNums.set(j, lastNums.get(j) + lastNums.get(j - 1));
            }
        }
        return result;
    }

    /**
     * 杨辉三角 2
     *
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        int length = rowIndex + 1;
        List<List<Integer>> numList = new ArrayList<>();
        //确立初态
        for (int i = 0; i < length; i++) {
            Integer[] nums = new Integer[i + 1];
            nums[0] = 1;
            nums[i] = 1;
            numList.add(Arrays.asList(nums));
        }
        //小于三则直接返回对应下标的数据
        if (length < 3) {
            return numList.get(rowIndex);
        }
        for (int i = 2; i < length; i++) {
            List<Integer> currNums = numList.get(i);
            List<Integer> lastNums = numList.get(i - 1);
            for (int j = 1; j < i; j++) {
                currNums.set(j, lastNums.get(j) + lastNums.get(j - 1));
            }
        }
        return numList.get(rowIndex);
    }

    /**
     * 斐波那契数列
     *
     * @param n
     * @return
     */
    public int fib(int n) {
        if (n == 1 || n == 0) return n;
        int[] fibs = new int[n + 1];
        fibs[0] = 0;
        fibs[1] = 1;
        for (int i = 2; i <= n; i++) {
            fibs[i] = fibs[i - 1] + fibs[i - 2];
        }
        return fibs[n];
    }

    /**
     * 392. 判断子序列
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        char[] chars = s.toCharArray();
        int targetLength = chars.length, index = 0;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (c == chars[index]) {
                index++;
                if (index == targetLength) return true;
            }
        }
        return false;
    }

    /**
     * 746. 使用最小花费爬楼梯
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 1) return cost[0];
        int[] count = new int[cost.length + 1];
        count[0] = 0;
        count[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            count[i] = Math.min(count[i - 1] + cost[i - 1], count[i - 2] + cost[i - 2]);
        }
        return count[cost.length];
    }

    /**
     * 除数博弈
     *
     * @param n
     * @return
     */
    public boolean divisorGame(int n) {
        boolean[] isWin = new boolean[n + 1];
        isWin[0] = false;
        isWin[1] = false;
        for (int i = 2; i <= n; i++) {
            isWin[i] = !isWin[i - 1];
        }
        return isWin[n];
    }

    /**
     * 第n个斐波那契数
     *
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        if (n == 0) return n;
        if (n == 1 || n == 2) return 1;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        nums[2] = 1;
        for (int i = 3; i <= n; i++) {
            nums[i] = nums[i - 1] + nums[i - 2] + nums[i - 3];
        }
        return nums[n];
    }

    /**
     * 1646. 获取生成数组中的最大值
     *
     * @param n
     * @return
     */
    public int getMaximumGenerated(int n) {
        if (n < 2) return n;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 0;
        for (int i = 1; i <= n / 2; i++) {
            nums[i * 2] = nums[i];
            max = nums[i * 2] > max ? nums[i * 2] : max;
            if (2 * i + 1 <= n) {
                nums[2 * i + 1] = nums[i + 1] + nums[i];
                max = nums[i * 2 + 1] > max ? nums[i * 2 + 1] : max;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.getRow(5));
    }
}
